#include "main.h"

// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq, int num_elements) {
	static int num_element = -1;
    num_element++;
    if (pre_order_seq[num_element] != '\0' && pre_order_seq[num_element] != '#') {
        (*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*root_pp)->data = pre_order_seq[num_element];
        create_tree(&((*root_pp)->leftChild), pre_order_seq, num_elements);
        create_tree(&((*root_pp)->rightChild), pre_order_seq, num_elements);
    }
    else {
        (*root_pp) = 0;
    }
	
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item))
{
	if(t!=0){
		visit(t->data);
		pre_order_traverse(t->leftChild,visit);
		pre_order_traverse(t->rightChild,visit);
	}
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item))
{
	if(t!=0){
		in_order_traverse(t->leftChild,visit);
		visit(t->data);
		in_order_traverse(t->rightChild,visit);
	}

}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
	if(t!=0){
		post_order_traverse(t->leftChild,visit);
		post_order_traverse(t->rightChild,visit);
		visit(t->data);
	}
}

// 可以无需更改本函数的实现
void visit(DataType item)
{
  printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x)
{
	if(root==0){
		return NULL;
	}else if((root->data)==x){
		return root;
	}
	BiTreeNode* a=search(root->leftChild,x);
	BiTreeNode* b=search(root->rightChild,x);
	if(a!=NULL){
		return a;
	}else{
		return b;
	}
	
}

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root)
{
	if((*root)!=0){
		destroy(&((*root)->leftChild));
		destroy(&((*root)->rightChild));
		free(*root);
	}
	
}

void main(void)
{
    void (*p)(DataType item) = visit;
    BiTreeNode* aa = 0;
    char po = 'A';
    create_tree(&aa, "ABC##DE#G##F###", 7);
    pre_order_traverse(aa, p);
    printf("%p", search(aa, po));
    destroy(&aa);
}